In 1983, Aldous proved that randomization can speedup local search. Forexample, it reduces the query complexity of local search over [1:n]^d fromTheta (n^{d-1}) to O (d^{1/2}n^{d/2}). It remains open whether randomizationhelps fixed-point computation. Inspired by this open problem and recentadvances on equilibrium computation, we have been fascinated by the followingquestion: Is a fixed-point or an equilibrium fundamentally harder to find than a localoptimum? In this paper, we give a nearly-tight bound of Omega(n)^{d-1} on therandomized query complexity for computing a fixed point of a discrete Brouwerfunction over [1:n]^d. Since the randomized query complexity of globaloptimization over [1:n]^d is Theta (n^{d}), the randomized query model over[1:n]^d strictly separates these three important search problems: Globaloptimization is harder than fixed-point computation, and fixed-pointcomputation is harder than local search. Our result indeed demonstrates thatrandomization does not help much in fixed-point computation in the query model;the deterministic complexity of this problem is Theta (n^{d-1}).
展开▼
